`
https://leetcode.cn/problems/word-break-ii/
`

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function (s, wordDict) {
  const res = []
  const track = []

  function backtrack(i) {
    // 找到一个答案
    if (i === s.length) {
      res.push(track.join(' '))
    }

    // 找每个单词是否能匹配
    for (const word of wordDict) {
      const len = word.length
      // 不能匹配
      if (s.length - i < len || s.substring(i, i + len) !== word) continue

      // 能匹配，尝试匹配下一段
      track.push(word)
      backtrack(i + len)
      track.pop()
    }
  }
  backtrack(0)

  return res
};